import java.util.LinkedList;
import java.util.NoSuchElementException;

public class doubleList<T> {
    //容器
    private static class Node<T> {
        T data;
        Node<T> pre;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    //首节点
    private Node<T> first;
    //尾节点
    private Node<T> last;
    //大小
    private int size;

    private Boolean isEmpty() {
        return size == 0;
    }

    //添加首节点
    public void addFirst(T Data) {
        Node<T> newNode = new Node<>(Data);
        if (isEmpty()) {
            first = newNode;
            last = newNode;
        } else {
            //建立双向指针然后进行交换
            newNode.next = first;
            first.pre = newNode;
            first = newNode;
        }
        size++;
    }

    //添加尾节点
    public void addLast(T Data) {
        Node<T> newNode = new Node<>(Data);
        if (isEmpty()) {
            first = newNode;
            last = newNode;
        } else {
            //与尾节点建立双向指针交换
            newNode.pre = last;
            last.next = newNode;
            last = newNode;
        }
        size++;
    }

    // 内部方法：获取指定位置节点
    public Node<T> getNode(Integer index) {
        //小于0，大于等于零需要调用特殊的方法3
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<T> current = first;

        for (Integer i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }
    //添加任意节点
    public void addAt(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if(index == 0){
            addFirst(data);
        }else if (index == size){
            addLast(data);
        }else {
            //设置双向链表断裂链接链接
            Node<T> newNode = new Node<>(data);
            Node<T> node = getNode(index);
            newNode.pre = node.pre;
            newNode.next = node;
            node.pre.next = newNode;
            node.pre = newNode;

            size++;
        }
    }
    //移除第一个节点
    public void removeFirst(){
        if (isEmpty()){
            throw new NoSuchElementException("List is empty");
        }
        if (size == 1){
            first = null;
            last = null;
        }else {
            first = first.next;
            first.pre =null;
        }
        size --;
    }
    //移除最后一个节点
    public  void removeLast(){
        if (isEmpty()){
            throw new NoSuchElementException("List is empty");
        }
        if (size == 1){
            last =null;
            first = null;
        }else {
            last = last.pre;
            last.next = null;
        }
        size --;
    }

    public void removeAt(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if(index == 0){
            removeFirst();
        }
        if (index == size){
            removeLast();
        }
        //设置双向链表断裂链接链接
        Node<T> node = getNode(index);
        node.pre.next = node.next;
        node.next.pre =node.pre;
        size--;
    }
    public void printList() {
        Node<T> current = first;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
    }


    public static void main(String[] args) {
        doubleList<Integer> integerdoubleList = new doubleList<>();
        integerdoubleList.addAt(0,1);
        integerdoubleList.addAt(0,2);
        integerdoubleList.addAt(0,3);
        integerdoubleList.addAt(0,4);
        integerdoubleList.addAt(3,5);
        integerdoubleList.removeAt(3);
        System.out.println(integerdoubleList.size());
        integerdoubleList.printList();
    }
    // 获取指定位置节点数据
    public T get(int index) {
        return getNode(index).data;
    }

    // 更新指定位置节点数据
    public void set(int index, T data) {
        getNode(index).data = data;
    }


    // 获取链表大小
    public int size() {
        return size;
    }

    // 清空链表
    public void clear() {
        first = last = null;
        size = 0;
    }


}
